from gurobipy import *
import aurora_network, path_selector
from enum import Enum
import numpy as np

class TrafficEngineeringClass(Enum):
	ECMP = 1
	WCMP = 2
	IDEAL = 3
	ROBUST_TE = 4
	ROBUST_WEIGHTED_TE = 5
	AVE_TE = 6
	MAX_TE = 7
	OBLIVIOUS = 8



class TrafficEngineer(object):
	#  all_interblock_paths : a 3D-array. all_interblock_paths[i][j] is an array of all paths from i to j
	def __init__(self, aurora_network, all_interblock_paths):
		self.aurora_network = aurora_network
		self.all_interblock_paths = all_interblock_paths
		return

	def get_filename_param(self):
		return "ecmp"

	# returns a string description of this class
	def get_string(self):
		return "ECMP"

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.ECMP

	# traditionally will implement ECMP
	def compute_path_weights(self, logical_topology_adj_matrix):
		nblocks = self.aurora_network.get_num_blocks()
		routing_weights = {}
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					num_paths = 0.
					for path in self.all_interblock_paths[i][j]:
						path_capacity = 10E10
						path_len = len(path) - 1
						curr_node = path[0]
						for path_index in range(1, path_len, 1):
							next_node = path[path_index]
							link_capacity = min(self.aurora_network.get_link_capacity(curr_node), self.aurora_network.get_link_capacity(next_node))
							path_capacity = min(path_capacity, logical_topology_adj_matrix[i][j] * link_capacity)
							curr_node = next_node
						if path_capacity > 0:
							routing_weights[path] = 1.
							num_paths += 1
						else:
							routing_weights[path] = 0.
					for path in self.all_interblock_paths[i][j]:
						routing_weights[path] /= num_paths
		#rweights_sum = np.zeros((nblocks,nblocks))
		#for path in routing_weights:
		#	src = path[0]
		#	dst = path[-1]
		#	rweights_sum[src][dst] += routing_weights[path]
		#print rweights_sum
		return routing_weights

# weight each path greedily, so that weights of all paths between two points sum to 1
class WCMPTrafficEngineer(TrafficEngineer):
	def __init__(self, aurora_network, all_interblock_paths):
		TrafficEngineer.__init__(self, aurora_network, all_interblock_paths)
		return

	def get_filename_param(self):
		return "wcmp"

	# returns a string description of this class
	def get_string(self):
		return "WCMP"

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.WCMP

	def compute_path_weights(self, logical_topology_adj_matrix):
		nblocks = self.aurora_network.get_num_blocks()
		routing_weights = {}
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					total_path_capacities = 0.
					for path in self.all_interblock_paths[i][j]:
						path_capacity = 10E15
						curr_node = path[0]
						for path_index in range(1, len(path), 1):
							next_node = path[path_index]
							link_capacity = min(self.aurora_network.get_link_capacity(curr_node), self.aurora_network.get_link_capacity(next_node))
							path_capacity = min(path_capacity, logical_topology_adj_matrix[curr_node][next_node] * link_capacity)
							curr_node = next_node
						total_path_capacities += path_capacity
						routing_weights[path] = path_capacity
					for path in self.all_interblock_paths[i][j]:
						if total_path_capacities == 0.:
							routing_weights[path] = 0.
						else:
							routing_weights[path] = routing_weights[path] / total_path_capacities
		return routing_weights

# weight each path greedily, so that weights of all paths between two points sum to 1
class ObliviousRouting(WCMPTrafficEngineer):
	def __init__(self, aurora_network, all_interblock_paths):
		WCMPTrafficEngineer.__init__(self, aurora_network, all_interblock_paths)
		return

	def get_filename_param(self):
		return "oblrouting"

	# returns a string description of this class
	def get_string(self):
		return "Oblivious Routing"

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.OBLIVIOUS

	### Given a logical topology, computes the traffic demand 
	def _compute_adversarial_tm_for_logical_topology(self, logical_topology_adj_matrix):
		#total_capacity = 0.
		nblocks = self.aurora_network.get_num_blocks()
		capacity_matrix = np.zeros((nblocks, nblocks,))
		max_cap = 0
		is_uniform = True
		prior_link_count = logical_topology_adj_matrix[0][1]
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					capacity = logical_topology_adj_matrix[i][j] * min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
					capacity_matrix[i][j] = capacity
					max_cap = max(max_cap, capacity)
					if is_uniform:
						if abs(logical_topology_adj_matrix[i][j] - prior_link_count) > 1.5:
							is_uniform = False
					#total_capacity = capacity
		if is_uniform:
			return capacity_matrix
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					capacity_matrix[i][j] = max(max_cap - capacity_matrix[i][j], 0.)

		return capacity_matrix

	def compute_path_weights(self, logical_topology_adj_matrix):
		nblocks = self.aurora_network.get_num_blocks()
		model = Model("Routing minimize MLU for traffic matrix")
		model.setParam( 'OutputFlag', False )
		mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=1., vtype=GRB.CONTINUOUS, name="mlu")
		traffic_matrix = self._compute_adversarial_tm_for_logical_topology(logical_topology_adj_matrix)
		routing_weight_vars = {}
		link_capacity_constraints = [None] * nblocks
		for i in range(nblocks):
			link_capacity_constraints[i] = [None] * nblocks
			for j in range(nblocks):
				if i != j:
					link_capacity_constraints[i][j] = LinExpr()
					weights_sum_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=0., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weights_sum_constraint += routing_weight_vars[path]
					model.addConstr(lhs=weights_sum_constraint, sense=GRB.EQUAL, rhs=1.)

		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path in self.all_interblock_paths[i][j]:
						src = path[0]
						dst = path[-1]
						curr_node = path[0]
						for path_hop in range(1, len(path), 1):
							next_node = path[path_hop]
							link_capacity_constraints[curr_node][next_node] += (routing_weight_vars[path] * traffic_matrix[i][j])
							curr_node = next_node

		## stage 2 : add the link utilization constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
					model.addConstr(lhs=link_capacity_constraints[i][j], sense=GRB.LESS_EQUAL, rhs=mlu * capacity * logical_topology_adj_matrix[i][j])
		# stage 3: set the objective
		model.setObjective(mlu, GRB.MINIMIZE)
		try: 
			model.optimize()
			routing_weights = {}
			for path in routing_weight_vars.keys():
				routing_weights[path] = routing_weight_vars[path].x
			return routing_weights
		except GurobiError as e1:
			print ("Error code " + str(e1. errno ) + ": " + str(e1))
			return None
		except AttributeError as e:
			print ("Oblivious Routing - Encountered an attribute error " + ": " + str(e))
			return None



# given a topology, and the traffic matrix, will compute the best case
class IdealTrafficEngineer(TrafficEngineer):
	def __init__(self, aurora_network, all_interblock_paths):
		TrafficEngineer.__init__(self, aurora_network, all_interblock_paths)
		return

	def get_filename_param(self):
		return "perfect"

	# returns a string description of this class
	def get_string(self):
		return "Perfect TE (Oracle Prediction)"

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.IDEAL

	def compute_path_weights(self, logical_topology_adj_matrix, traffic_matrix):
		nblocks = self.aurora_network.get_num_blocks()
		model = Model("Routing minimize MLU for traffic matrix")
		model.setParam( 'OutputFlag', False )
		mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=1., vtype=GRB.CONTINUOUS, name="mlu")
		routing_weight_vars = {}
		link_capacity_constraints = [None] * nblocks
		for i in range(nblocks):
			link_capacity_constraints[i] = [None] * nblocks
			for j in range(nblocks):
				if i != j:
					link_capacity_constraints[i][j] = LinExpr()
					weights_sum_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=0., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weights_sum_constraint += routing_weight_vars[path]
					model.addConstr(lhs=weights_sum_constraint, sense=GRB.EQUAL, rhs=1.)

		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path in self.all_interblock_paths[i][j]:
						src = path[0]
						dst = path[-1]
						curr_node = path[0]
						for path_hop in range(1, len(path), 1):
							next_node = path[path_hop]
							link_capacity_constraints[curr_node][next_node] += (routing_weight_vars[path] * traffic_matrix[i][j])
							curr_node = next_node

		## stage 2 : add the link utilization constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
					model.addConstr(lhs=link_capacity_constraints[i][j], sense=GRB.LESS_EQUAL, rhs=mlu * capacity * logical_topology_adj_matrix[i][j])
		# stage 3: set the objective
		model.setObjective(mlu, GRB.MINIMIZE)
		try: 
			model.optimize()
			routing_weights = {}
			for path in routing_weight_vars.keys():
				routing_weights[path] = routing_weight_vars[path].x
			return routing_weights
		except GurobiError as e1:
			print ("Error code " + str(e1. errno ) + ": " + str(e1))
			return None
		except AttributeError as e:
			print ("Ideal Traffic Engineering - Encountered an attribute error " + ": " + str(e))
			return None

	# minimizes MLU subject to the fact that hop count equals to the argument
	def compute_path_weights_fix_avehopcount(self, logical_topology_adj_matrix, traffic_matrix, avehopcount):
		assert(avehopcount >= 1 and avehopcount <= 2)
		nblocks = self.aurora_network.get_num_blocks()
		model = Model("Routing minimize MLU for traffic matrix")
		model.setParam( 'OutputFlag', False )
		mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=1., vtype=GRB.CONTINUOUS, name="mlu")
		routing_weight_vars = {}
		link_capacity_constraints = [None] * nblocks
		for i in range(nblocks):
			link_capacity_constraints[i] = [None] * nblocks
			for j in range(nblocks):
				if i != j:
					link_capacity_constraints[i][j] = LinExpr()
					weights_sum_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=GRB.INFINITY, obj=0., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weights_sum_constraint += routing_weight_vars[path]
					model.addConstr(lhs=traffic_matrix[i][j], sense=GRB.EQUAL, rhs=weights_sum_constraint)

		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path in self.all_interblock_paths[i][j]:
						src = path[0]
						dst = path[-1]
						curr_node = path[0]
						for path_hop in range(1, len(path), 1):
							next_node = path[path_hop]
							link_capacity_constraints[curr_node][next_node] += routing_weight_vars[path]
							curr_node = next_node

		## stage 2 : add the link utilization constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
					model.addConstr(lhs=link_capacity_constraints[i][j], sense=GRB.LESS_EQUAL, rhs=mlu * capacity * logical_topology_adj_matrix[i][j])

		## stage 2.5 : fix the hop count
		hopcount_constraint = LinExpr()
		total_traffic = 0.
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j and traffic_matrix[i][j] > 0:
					total_traffic += traffic_matrix[i][j]
					for path in self.all_interblock_paths[i][j]:
						hc = 1.
						if len(path) > 2:
							hc = 2.
						hopcount_constraint += (hc * routing_weight_vars[path])
		model.addConstr(lhs=hopcount_constraint, sense=GRB.EQUAL, rhs=avehopcount * total_traffic)
		#print("total traffic is : {} avehopcount is: {}".format(total_traffic, avehopcount))
		#model.addConstr(lhs=0 * avehopcount * total_traffic, sense=GRB.LESS_EQUAL, rhs=hopcount_constraint)
		#model.addConstr(lhs=hopcount_constraint, sense=GRB.LESS_EQUAL, rhs=100. * avehopcount * total_traffic)

		# stage 3: set the objective
		model.setObjective(mlu, GRB.MINIMIZE)
		try: 
			model.optimize()
			routing_weights = {}
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						if traffic_matrix[i][j] > 0:
							traffic_sum = 0.
							for path in self.all_interblock_paths[i][j]:
								traffic_sum += routing_weight_vars[path].x
								routing_weights[path] = routing_weight_vars[path].x
							for path in self.all_interblock_paths[i][j]:
								routing_weights[path] /= traffic_sum
						else:
							# ecmp otherwise
							ratio = 1./len(self.all_interblock_paths[i][j])
							for path in self.all_interblock_paths[i][j]:
								routing_weights[path] = ratio
			return routing_weights
		except GurobiError as e1:
			print ("Error code " + str(e1. errno ) + ": " + str(e1))
			return None
		except AttributeError as e:
			print ("Ideal Traffic Engineering - same hop count Encountered an attribute error " + ": " + str(e))
			return None

class RobustMultiClusterTrafficEngineer(TrafficEngineer):
	## Takes in two new variables:
	## update_frequency - how much time in-between every traffic engineering events
	def __init__(self, aurora_network, all_interblock_paths, update_frequency, training_length, num_k, reduce_multihop=False, ignore_flows=None):
		TrafficEngineer.__init__(self, aurora_network, all_interblock_paths)
		self.flow_pairs_to_ignore = ignore_flows
		self.update_frequency = update_frequency
		self.training_length = training_length
		self.reduce_multihop = reduce_multihop
		self.num_k = num_k
		return

	def get_filename_param(self):
		return "robustte_r{}t{}c{}".format(self.update_frequency, self.training_length, self.num_k)

	def get_num_clusters_for_training(self):
		return self.num_k
	# returns a string description of this class
	def get_string(self):
		return "Robust TE, {} clusters, w/ update_frequency: {} and training_length: {}".format(self.num_k, self.update_frequency, self.training_length)

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.ROBUST_TE

	## While preserving the worst case mlu, we want to reduce reliance on non-minimal paths
	def _minimize_multihop(self, logical_topology_adj_matrix, traffic_matrices, worst_case_mlu):
		routing_weights = {}
		nblocks = self.aurora_network.get_num_blocks()
		num_tm = len(traffic_matrices)
		model = Model("Minimize routing weights on multihops")
		model.setParam( 'OutputFlag', False )
		routing_weight_vars = {}
		link_capacity_constraints = [None] * num_tm
		for k in range(num_tm):
			link_capacity_constraints[k] = [None] * nblocks
			for i in range(nblocks):
				link_capacity_constraints[k][i] = [None] * nblocks
				for j in range(nblocks):
					if i != j:
						link_capacity_constraints[k][i][j] = LinExpr()
						#routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=1., vtype=GRB.CONTINUOUS, name="w_{},{}".format(i,j))
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=0, vtype=GRB.CONTINUOUS, name="w_{}".format(path))

		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		tm_index = 0
		for tm in traffic_matrices:
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						for path in self.all_interblock_paths[i][j]:
							src = path[0]
							for path_hop in range(1, len(path), 1):
								dst = path[path_hop]
								link_capacity_constraints[tm_index][src][dst] += (routing_weight_vars[path] * tm[i][j])
								src = dst
						#for k in range(nblocks):
						#	if k != i and k != j:
						#		lu_constraint += routing_weight_vars[(i,k,j)] * tm[i][k] + routing_weight_vars[(k,j,i)] * tm[k][j]
						#		weight_constraint += routing_weight_vars[(i, j, k,)]
						#model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=mlu * capacity_matrix[i][j] * logical_topology_adj_matrix[i][j])
						#model.addConstr(lhs=weight_constraint, sense=GRB.EQUAL, rhs=1.)
			tm_index += 1
		## stage 2 : add the link utilization constraints
		for tm_index in range(num_tm):
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						lu_constraint = link_capacity_constraints[tm_index][i][j]
						capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
						model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=worst_case_mlu * capacity * logical_topology_adj_matrix[i][j])
						weight_constraint = LinExpr()
						for path in self.all_interblock_paths[i][j]:
							weight_constraint += routing_weight_vars[path]
						model.addConstr(lhs=weight_constraint, sense=GRB.EQUAL, rhs=1.)
		# stage 3: set the objective
		objective_function = LinExpr()
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path in self.all_interblock_paths[i][j]:				
						if len(path) > 2:
							objective_function += (routing_weight_vars[path] * routing_weight_vars[path])
		model.setObjective(objective_function, GRB.MINIMIZE)
		try: 
			model.optimize()
			routing_weights = {}
			for path in routing_weight_vars.keys():
				routing_weights[path] = routing_weight_vars[path].x
			return routing_weights
		except GurobiError as e:
			print ("Error code " + str(e. errno ) + ": " + str(e))
			return None
		except AttributeError :
			print ("Encountered an attribute error ")
			return None
		return routing_weights

	#def _compute_mlu(self, traffic_matrices, capacity_matrix, all_paths):
	## Currently does not involve another step that reduces hop count
	def _compute_path_weights_minimize_worstcase_mlu(self, logical_topology_adj_matrix, traffic_matrices):
		nblocks = self.aurora_network.get_num_blocks()
		num_tm = len(traffic_matrices)
		model = Model("Routing minimize MLU for all traffic matrices")
		model.setParam( 'OutputFlag', False )
		mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=0, vtype=GRB.CONTINUOUS, name="mlu")
		routing_weight_vars = {}
		link_capacity_constraints = [None] * num_tm
		for k in range(num_tm):
			link_capacity_constraints[k] = [None] * nblocks
			for i in range(nblocks):
				link_capacity_constraints[k][i] = [None] * nblocks
				for j in range(nblocks):
					if i != j:
						link_capacity_constraints[k][i][j] = LinExpr()
						#routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=1., vtype=GRB.CONTINUOUS, name="w_{},{}".format(i,j))
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					weight_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=1., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weight_constraint += routing_weight_vars[path]
					model.addConstr(lhs=weight_constraint, sense=GRB.EQUAL, rhs=1.)


		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for tm, tm_index in zip(traffic_matrices, range(num_tm)):
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						for path in self.all_interblock_paths[i][j]:
							src = path[0]
							for path_hop in range(1, len(path), 1):
								dst = path[path_hop]
								link_capacity_constraints[tm_index][src][dst] += (routing_weight_vars[path] * tm[i][j])
								src = dst
						#for k in range(nblocks):
						#	if k != i and k != j:
						#		lu_constraint += routing_weight_vars[(i,k,j)] * tm[i][k] + routing_weight_vars[(k,j,i)] * tm[k][j]
						#		weight_constraint += routing_weight_vars[(i, j, k,)]
						#model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=mlu * capacity_matrix[i][j] * logical_topology_adj_matrix[i][j])
						#model.addConstr(lhs=weight_constraint, sense=GRB.EQUAL, rhs=1.)
		## stage 2 : add the link utilization constraints to the model
		for tm_index in range(num_tm):
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						lu_constraint = link_capacity_constraints[tm_index][i][j]
						capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
						model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=mlu * capacity * logical_topology_adj_matrix[i][j])
		# stage 3: set the objective
		model.setObjective(mlu, GRB.MINIMIZE)
		try: 
			model.optimize()
			routing_weights = {}
			for path in routing_weight_vars.keys():
				routing_weights[path] = routing_weight_vars[path].x
			return routing_weights, mlu.x
		except GurobiError as e:
			print ("Error code " + str(e. errno ) + ": " + str(e))
			return None
		except AttributeError :
			print ("Encountered an attribute error ")
			return None

	def compute_path_weights(self, logical_topology_adj_matrix, traffic_matrices, spare_traffic=0.1, fraction_threshold=0.002):
		## newly added for robustness
		nblocks = self.aurora_network.get_num_blocks()
		'''
		for traffic_matrix in traffic_matrices:
			traffic_sum = sum([sum(x) for x in traffic_matrix])
			reset_num_entries = 0
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j and self.flow_pairs_to_ignore is not None and (i,j) not in self.flow_pairs_to_ignore:
						if traffic_matrix[i][j] < fraction_threshold * traffic_sum:
							reset_num_entries += 1
			if reset_num_entries > 0:
				scratch_traffic = (spare_traffic * traffic_sum) / (1 - spare_traffic) / float(reset_num_entries)
				for i in range(nblocks):
					for j in range(nblocks):
						if i != j and self.flow_pairs_to_ignore is not None and (i,j) not in self.flow_pairs_to_ignore:
							if traffic_matrix[i][j] < fraction_threshold * traffic_sum:
								traffic_matrix[i][j] = scratch_traffic
		## newly added for robustness
		#assert(len(traffic_matrices) == self.num_k)
		'''
		print("brrrrp brrrrp")
		routing_weights, worst_case_mlu = self._compute_path_weights_minimize_worstcase_mlu(logical_topology_adj_matrix, traffic_matrices)
		if self.reduce_multihop:
			routing_weights = self._minimize_multihop(logical_topology_adj_matrix, traffic_matrices, worst_case_mlu)
		return routing_weights


# same implementation as RobustMultiClusterTrafficEngineer but we weigh traffic matrix with its max scale up factor
class RobustMultiClusterScaleUpWeightedTrafficEngineer(RobustMultiClusterTrafficEngineer):
	## Takes in two new variables:
	## update_frequency - how much time in-between every traffic engineering events
	def __init__(self, aurora_network, all_interblock_paths, update_frequency, training_length, num_k, reduce_multihop=False, ignore_flows=None):
		RobustMultiClusterTrafficEngineer.__init__(self, aurora_network, all_interblock_paths, update_frequency, training_length, num_k, reduce_multihop=reduce_multihop)
		self.flow_pairs_to_ignore = ignore_flows
		self.update_frequency = update_frequency
		self.training_length = training_length
		self.num_k = num_k
		return

	def get_filename_param(self):
		return "robustweightedte_r{}t{}c{}".format(self.update_frequency, self.training_length, self.num_k)

	def get_num_clusters_for_training(self):
		return self.num_k
	# returns a string description of this class
	def get_string(self):
		return "Robust scale up weighted TE, {} clusters, w/ update_frequency: {} and training_length: {}".format(self.num_k, self.update_frequency, self.training_length)

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.ROBUST_WEIGHTED_TE

	## Currently does not involve another step that reduces hop count
	def _compute_max_traffic_scaleup(self, logical_topology_adj_matrix, traffic_matrix):
		nblocks = self.aurora_network.get_num_blocks()
		model = Model("Find the max traffic scale up")
		model.setParam( 'OutputFlag', False )
		mu = model.addVar(lb=0., ub=GRB.INFINITY, obj=0, vtype=GRB.CONTINUOUS, name="mu")
		routing_weight_vars = {}
		link_capacity_constraints = [None] * nblocks
		for i in range(nblocks):
			link_capacity_constraints[i] = [None] * nblocks
			for j in range(nblocks):
				if i != j:
					link_capacity_constraints[i][j] = LinExpr()
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					weight_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=GRB.INFINITY, obj=1., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weight_constraint += routing_weight_vars[path]
					model.addConstr(lhs=mu * traffic_matrix[i][j], sense=GRB.LESS_EQUAL, rhs=weight_constraint)

		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path in self.all_interblock_paths[i][j]:
						src = path[0]
						for path_hop in range(1, len(path), 1):
							dst = path[path_hop]
							link_capacity_constraints[src][dst] += (routing_weight_vars[path])
							src = dst
		## stage 2 : add the link utilization constraints to the model
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					lu_constraint = link_capacity_constraints[i][j]
					capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
					model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=capacity * logical_topology_adj_matrix[i][j])
		# stage 3: set the objective
		model.setObjective(mu, GRB.MAXIMIZE)
		try: 
			model.optimize()
			return mu.x
		except GurobiError as e:
			print ("Error code " + str(e. errno ) + ": " + str(e))
			return None
		except AttributeError :
			print ("Encountered an attribute error ")
			return None


	def compute_path_weights(self, logical_topology_adj_matrix, traffic_matrices, spare_traffic=0.1, fraction_threshold=0.001):
		## newly added for robustness
		nblocks = self.aurora_network.get_num_blocks()
		for traffic_matrix in traffic_matrices:
			traffic_sum = sum([sum(x) for x in traffic_matrix])
			reset_num_entries = 0
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j and self.flow_pairs_to_ignore is not None and (i,j) not in self.flow_pairs_to_ignore:
						if traffic_matrix[i][j] < fraction_threshold * traffic_sum:
							reset_num_entries += 1
			if reset_num_entries > 0:
				scratch_traffic = (spare_traffic * traffic_sum) / (1 - spare_traffic) / float(reset_num_entries)
				for i in range(nblocks):
					for j in range(nblocks):
						if i != j and self.flow_pairs_to_ignore is not None and (i,j) not in self.flow_pairs_to_ignore:
							if traffic_matrix[i][j] < fraction_threshold * traffic_sum:
								traffic_matrix[i][j] = scratch_traffic
		#for traffic_matrix in traffic_matrices:
		#	traffic_sum = sum([sum(x) for x in traffic_matrix])
		#	reset_num_entries = 0
		#	for i in range(nblocks):
		#		for j in range(nblocks):
		#			if i != j:
		#				if traffic_matrix[i][j] < 0.0001:
		#					reset_num_entries += 1
		#	for i in range(nblocks):
		#		for j in range(nblocks):
		#			if i != j:
		#				if traffic_matrix[i][j] < 0.0001:
		#					traffic_matrix[i][j] = (spare_traffic * traffic_sum) / (1 - spare_traffic) / float(reset_num_entries)
		## newly added for robustness
		individual_scale_ups = []
		for tm_index in range(len(traffic_matrices)):
			scaleup_factor = self._compute_max_traffic_scaleup(logical_topology_adj_matrix, traffic_matrices[tm_index])
			individual_scale_ups.append(scaleup_factor)
			# now, scale each entry in traffic matrix by scaleup factor
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						traffic_matrices[tm_index][i][j] *= scaleup_factor
		routing_weights, worst_case_mlu = self._compute_path_weights_minimize_worstcase_mlu(logical_topology_adj_matrix, traffic_matrices)
		print("\n\n\nindividual scaleups for multi traffic te is : {}".format(individual_scale_ups))
		print("worst case mlu for multi traffic te is : {}\n\n\n".format(worst_case_mlu))
		if self.reduce_multihop:
			routing_weights = self._minimize_multihop(logical_topology_adj_matrix, traffic_matrices, worst_case_mlu)
		#### Jason Newlu added hack (BEGIN)
		if self.aurora_network.get_dcn_name() == "ju1_dls08":
			for (i,j) in [(6,11), (8,11), (12,11)]:
				path_total_capacity = 0.
				for path in self.all_interblock_paths[i][j]:
					curr_node = path[0]
					path_capacity = 10E15
					for index in range(1, len(path), 1):
						next_node = path[index]
						cap = min(self.aurora_network.get_link_capacity(curr_node), self.aurora_network.get_link_capacity(next_node))
						path_capacity = min(path_capacity, logical_topology_adj_matrix[curr_node][next_node] * cap)
						curr_node = next_node
					path_total_capacity += path_capacity
					routing_weights[path] = path_capacity
				for path in self.all_interblock_paths[i][j]:
					routing_weights[path] /= path_total_capacity
		#### Jason Newlu added hack (END)
		return routing_weights


# same implementation as RobustMultiClusterTrafficEngineer but we weigh traffic matrix with its max scale up factor
class RobustMultiClusterScaleUpWeightedTrafficEngineerHeuristic(RobustMultiClusterScaleUpWeightedTrafficEngineer):
	## Takes in two new variables:
	## update_frequency - how much time in-between every traffic engineering events
	def __init__(self, aurora_network, all_interblock_paths, update_frequency, training_length, num_k, reduce_multihop=False, ignore_flows=None):
		RobustMultiClusterScaleUpWeightedTrafficEngineer.__init__(self, aurora_network, all_interblock_paths, update_frequency, training_length, num_k, reduce_multihop=reduce_multihop)
		self.flow_pairs_to_ignore = ignore_flows
		self.update_frequency = update_frequency
		self.training_length = training_length
		self.num_k = num_k
		return

	def get_filename_param(self):
		return "robustweightedheuristicte_r{}t{}c{}".format(self.update_frequency, self.training_length, self.num_k)

	def get_num_clusters_for_training(self):
		return self.num_k
	# returns a string description of this class
	def get_string(self):
		return "Robust scale up weighted heuristic TE, {} clusters, w/ update_frequency: {} and training_length: {}".format(self.num_k, self.update_frequency, self.training_length)

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.ROBUST_WEIGHTED_TE

	## Currently does not involve another step that reduces hop count
	def _compute_max_traffic_scaleup(self, logical_topology_adj_matrix, traffic_matrix):
		nblocks = self.aurora_network.get_num_blocks()
		model = Model("Find the max traffic scale up")
		model.setParam( 'OutputFlag', False )
		mu = model.addVar(lb=0., ub=GRB.INFINITY, obj=0, vtype=GRB.CONTINUOUS, name="mu")
		routing_weight_vars = {}
		link_capacity_constraints = [None] * nblocks
		for i in range(nblocks):
			link_capacity_constraints[i] = [None] * nblocks
			for j in range(nblocks):
				if i != j:
					link_capacity_constraints[i][j] = LinExpr()
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					weight_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=GRB.INFINITY, obj=1., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weight_constraint += routing_weight_vars[path]
					model.addConstr(lhs=mu * traffic_matrix[i][j], sense=GRB.LESS_EQUAL, rhs=weight_constraint)

		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path in self.all_interblock_paths[i][j]:
						src = path[0]
						for path_hop in range(1, len(path), 1):
							dst = path[path_hop]
							link_capacity_constraints[src][dst] += (routing_weight_vars[path])
							src = dst
		## stage 2 : add the link utilization constraints to the model
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					lu_constraint = link_capacity_constraints[i][j]
					capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
					model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=capacity * logical_topology_adj_matrix[i][j])
		# stage 3: set the objective
		model.setObjective(mu, GRB.MAXIMIZE)
		try: 
			model.optimize()
			return mu.x
		except GurobiError as e:
			print ("Error code " + str(e. errno ) + ": " + str(e))
			return None
		except AttributeError :
			print ("Encountered an attribute error ")
			return None


	def compute_path_weights(self, logical_topology_adj_matrix, traffic_matrices, spare_traffic=0.1, fraction_threshold=0.001, cutoff=0.002):
		## newly added for robustness
		nblocks = self.aurora_network.get_num_blocks()
		for traffic_matrix in traffic_matrices:
			traffic_sum = sum([sum(x) for x in traffic_matrix])
			reset_num_entries = 0
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j and self.flow_pairs_to_ignore is not None and (i,j) not in self.flow_pairs_to_ignore:
						if traffic_matrix[i][j] < fraction_threshold * traffic_sum:
							reset_num_entries += 1
			if reset_num_entries > 0:
				scratch_traffic = (spare_traffic * traffic_sum) / (1 - spare_traffic) / float(reset_num_entries)
				for i in range(nblocks):
					for j in range(nblocks):
						if i != j and self.flow_pairs_to_ignore is not None and (i,j) not in self.flow_pairs_to_ignore:
							if traffic_matrix[i][j] < fraction_threshold * traffic_sum:
								traffic_matrix[i][j] = scratch_traffic
		#for traffic_matrix in traffic_matrices:
		#	traffic_sum = sum([sum(x) for x in traffic_matrix])
		#	reset_num_entries = 0
		#	for i in range(nblocks):
		#		for j in range(nblocks):
		#			if i != j:
		#				if traffic_matrix[i][j] < 0.0001:
		#					reset_num_entries += 1
		#	for i in range(nblocks):
		#		for j in range(nblocks):
		#			if i != j:
		#				if traffic_matrix[i][j] < 0.0001:
		#					traffic_matrix[i][j] = (spare_traffic * traffic_sum) / (1 - spare_traffic) / float(reset_num_entries)
		## newly added for robustness
		for tm_index in range(len(traffic_matrices)):
			scaleup_factor = self._compute_max_traffic_scaleup(logical_topology_adj_matrix, traffic_matrices[tm_index])
			# now, scale each entry in traffic matrix by scaleup factor
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						traffic_matrices[tm_index][i][j] *= scaleup_factor
		routing_weights, worst_case_mlu = self._compute_path_weights_minimize_worstcase_mlu(logical_topology_adj_matrix, traffic_matrices)
		if self.reduce_multihop:
			routing_weights = self._minimize_multihop(logical_topology_adj_matrix, traffic_matrices, worst_case_mlu)
		#### Jason Newlu added hack (BEGIN)
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					max_entry = 0.
					for k in range(len(traffic_matrices)):
						max_entry = max(max_entry, traffic_matrices[k][i][j])
					if max_entry <= cutoff:
						path_total_capacity = 0.
						for path in self.all_interblock_paths[i][j]:
							curr_node = path[0]
							path_capacity = 10E15
							for index in range(1, len(path), 1):
								next_node = path[index]
								cap = min(self.aurora_network.get_link_capacity(curr_node), self.aurora_network.get_link_capacity(next_node))
								path_capacity = min(path_capacity, logical_topology_adj_matrix[curr_node][next_node] * cap)
								curr_node = next_node
							path_total_capacity += path_capacity
							routing_weights[path] = path_capacity
						for path in self.all_interblock_paths[i][j]:
							routing_weights[path] /= path_total_capacity
		#### Jason Newlu added hack (END)
		return routing_weights

class HistoricalAveTrafficEngineer(TrafficEngineer):
	## Takes in two new variables:
	## update_frequency - how much time in-between every traffic engineering events
	def __init__(self, aurora_network, all_interblock_paths, update_frequency, training_length):
		TrafficEngineer.__init__(self, aurora_network, all_interblock_paths)
		self.update_frequency = update_frequency
		self.training_length = training_length
		return

	def get_filename_param(self):
		return "avete_r{}t{}".format(self.update_frequency, self.training_length)

	# returns a string description of this class
	def get_string(self):
		return "Ave TE, w/ update_frequency: {} and training_length: {}".format(self.update_frequency, self.training_length)

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.AVE_TE

	#def _compute_mlu(self, traffic_matrices, capacity_matrix, all_paths):
	## Currently does not involve another step that reduces hop count
	def _compute_path_weights_minimize_worstcase_mlu(self, logical_topology_adj_matrix, traffic_matrix):
		nblocks = self.aurora_network.get_num_blocks()
		model = Model("Routing minimize MLU for all traffic matrices")
		model.setParam( 'OutputFlag', False )
		mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=0, vtype=GRB.CONTINUOUS, name="mlu")
		routing_weight_vars = {}
		link_capacity_constraints = [None] * nblocks
		for i in range(nblocks):
			link_capacity_constraints[i] = [None] * nblocks
			for j in range(nblocks):
				if i != j:
					link_capacity_constraints[i][j] = LinExpr()
					#routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=1., vtype=GRB.CONTINUOUS, name="w_{},{}".format(i,j))
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					weight_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=1., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weight_constraint += routing_weight_vars[path]
					model.addConstr(lhs=weight_constraint, sense=GRB.EQUAL, rhs=1.)


		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path in self.all_interblock_paths[i][j]:
						src = path[0]
						for path_hop in range(1, len(path), 1):
							dst = path[path_hop]
							link_capacity_constraints[src][dst] += (routing_weight_vars[path] * traffic_matrix[i][j])
							src = dst
		## stage 2 : add the link utilization constraints to the model
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					lu_constraint = link_capacity_constraints[i][j]
					capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
					model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=mlu * capacity * logical_topology_adj_matrix[i][j])
		# stage 3: set the objective
		model.setObjective(mlu, GRB.MINIMIZE)
		try: 
			model.optimize()
			routing_weights = {}
			for path in routing_weight_vars.keys():
				routing_weights[path] = routing_weight_vars[path].x
			return routing_weights
		except GurobiError as e:
			print ("Error code " + str(e. errno ) + ": " + str(e))
			return None
		except AttributeError :
			print ("Encountered an attribute error ")
			return None

	def compute_path_weights(self, logical_topology_adj_matrix, traffic_matrices):
		nblocks = self.aurora_network.get_num_blocks()
		expected_traffic_matrix = np.zeros((nblocks, nblocks))
		num_tms = len(traffic_matrices)
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for tm_index in range(num_tms):
						expected_traffic_matrix[i][j] += (traffic_matrices[tm_index][i][j] / num_tms)
		#for i in range(nblocks):
		#	for j in range(nblocks):
		#		if i != j and expected_traffic_matrix[i][j] == 0:
		#			expected_traffic_matrix[i][j] = 50.
		routing_weights = self._compute_path_weights_minimize_worstcase_mlu(logical_topology_adj_matrix, expected_traffic_matrix)
		return routing_weights


class HistoricalMaxTrafficEngineer(TrafficEngineer):
	## Takes in two new variables:
	## update_frequency - how much time in-between every traffic engineering events
	def __init__(self, aurora_network, all_interblock_paths, update_frequency, training_length):
		TrafficEngineer.__init__(self, aurora_network, all_interblock_paths)
		self.update_frequency = update_frequency
		self.training_length = training_length
		return

	def get_filename_param(self):
		return "maxte_r{}t{}".format(self.update_frequency, self.training_length)

	# returns a string description of this class
	def get_string(self):
		return "Max TE, w/ update_frequency: {} and training_length: {}".format(self.update_frequency, self.training_length)

	def traffic_engineering_class(self):
		return TrafficEngineeringClass.MAX_TE

	#def _compute_mlu(self, traffic_matrices, capacity_matrix, all_paths):
	## Currently does not involve another step that reduces hop count
	def _compute_path_weights_minimize_worstcase_mlu(self, logical_topology_adj_matrix, traffic_matrix):
		nblocks = self.aurora_network.get_num_blocks()
		model = Model("Routing minimize MLU for all traffic matrices")
		model.setParam( 'OutputFlag', False )
		mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=0, vtype=GRB.CONTINUOUS, name="mlu")
		routing_weight_vars = {}
		link_capacity_constraints = [None] * nblocks
		for i in range(nblocks):
			link_capacity_constraints[i] = [None] * nblocks
			for j in range(nblocks):
				if i != j:
					link_capacity_constraints[i][j] = LinExpr()
					#routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=1., vtype=GRB.CONTINUOUS, name="w_{},{}".format(i,j))
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					weight_constraint = LinExpr()
					for path in self.all_interblock_paths[i][j]:
						routing_weight_vars[path] = model.addVar(lb=0., ub=1., obj=1., vtype=GRB.CONTINUOUS, name="w_{}".format(path))
						weight_constraint += routing_weight_vars[path]
					model.addConstr(lhs=weight_constraint, sense=GRB.EQUAL, rhs=1.)


		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path in self.all_interblock_paths[i][j]:
						src = path[0]
						for path_hop in range(1, len(path), 1):
							dst = path[path_hop]
							link_capacity_constraints[src][dst] += (routing_weight_vars[path] * traffic_matrix[i][j])
							src = dst
		## stage 2 : add the link utilization constraints to the model
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					lu_constraint = link_capacity_constraints[i][j]
					capacity = min(self.aurora_network.get_link_capacity(i), self.aurora_network.get_link_capacity(j))
					model.addConstr(lhs=lu_constraint, sense=GRB.LESS_EQUAL, rhs=mlu * capacity * logical_topology_adj_matrix[i][j])
		# stage 3: set the objective
		model.setObjective(mlu, GRB.MINIMIZE)
		try: 
			model.optimize()
			routing_weights = {}
			for path in routing_weight_vars.keys():
				routing_weights[path] = routing_weight_vars[path].x
			return routing_weights
		except GurobiError as e:
			print ("Error code " + str(e. errno ) + ": " + str(e))
			return None
		except AttributeError :
			print ("Encountered an attribute error ")
			return None

	def compute_path_weights(self, logical_topology_adj_matrix, traffic_matrices):
		nblocks = self.aurora_network.get_num_blocks()
		max_tm = np.zeros((nblocks, nblocks))
		num_tms = len(traffic_matrices)
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for tm_index in range(num_tms):
						max_tm[i][j] = max(float(traffic_matrices[tm_index][i][j]), max_tm[i][j])
		#for i in range(nblocks):
		#	for j in range(nblocks):
		#		if i != j and max_tm[i][j] == 0:
		#			max_tm[i][j] = 50.
		routing_weights = self._compute_path_weights_minimize_worstcase_mlu(logical_topology_adj_matrix, max_tm)
		return routing_weights


## Bounded WCMP
def bounded_wcmp_path_weights(nblocks, link_capacity, logical_topology_adj_matrix, traffic_matrices):
	egress_bound = [0] * nblocks
	ingress_bound = [0] * nblocks
	## Step 1 : compute the pod egress and ingress bounds
	max_tm = np.zeros((nblocks, nblocks,))
	for tm in traffic_matrices:
		for pod in range(nblocks):
			pod_egress = sum(tm[pod])
			pod_ingress = 0
			for target_pod in range(nblocks):
				pod_ingress += tm[target_pod][pod]
				max_tm[pod][target_pod] = max(max_tm[pod][target_pod], tm[pod][target_pod])
			egress_bound[pod] = max(egress_bound[pod], pod_egress)
			ingress_bound[pod] = max(ingress_bound[pod], pod_ingress)


	# Step 2 : Initialize the optimization variables
	model = Model("Bounded WCMP")
	model.setParam( 'OutputFlag', False )
	mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=0, vtype=GRB.CONTINUOUS, name="mlu")
	routing_weights_var = [None] * (nblocks + 1)
	for index in range(nblocks + 1):
		routing_weights_var[index] = model.addVar(lb=0., ub=1, obj=0, vtype=GRB.CONTINUOUS, name="w_{}".format(index))

	## map each routing weight to the actual index
	routing_paths_to_index_map = {}
	for i in range(nblocks):
		for j in range(nblocks):
			if i != j:
				## via pod
				routing_paths_to_index_map[(i, j)] = 0
				for k in range(nblocks):
					if k != i and k != j:
						# follow i
						routing_paths_to_index_map[(i, k, j)] = k + 1

	## Step 3 : Start programming the constraints
	## Constraint Type 1 : weights must sum to 1
	weight_constraint = LinExpr()
	for index in range(nblocks + 1):
		weight_constraint += routing_weights_var[index]
	model.addConstr(lhs=weight_constraint,sense=GRB.EQUAL,rhs=1)
	## Constraint Type 2 : mlu constraint
	for i in range(nblocks):
		for j in range(nblocks):
			if i != j:
				mlu_constraint = LinExpr()
				Zi = egress_bound[i]
				Zj = ingress_bound[j]
				Uij = max_tm[i][j]
				w0 = routing_weights_var[0]
				wi = routing_weights_var[i + 1]
				wj = routing_weights_var[j + 1]
				mlu_constraint = Zi * wj + Zj * wi + w0 * Uij
				model.addConstr(lhs=mlu_constraint, sense=GRB.LESS_EQUAL, rhs=mlu * link_capacity * logical_topology_adj_matrix[i][j])
	
	## Step 4 : insert the objective function
	model.setObjective(mlu, GRB.MINIMIZE)
	try:
		model.optimize()
		print("Bounded WCMP - MLU : {}".format(mlu.x))
		routing_weights = {}
		block_pair_utilization = np.zeros((nblocks, nblocks))
		
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					direct_path = (i,j)
					direct_path_weight = routing_weights_var[0].x + routing_weights_var[i + 1].x + routing_weights_var[j + 1].x
					routing_weights[direct_path] = direct_path_weight
					for k in range(nblocks):
						if k != i and k != j:
							indirect_path = (i,k,j)
							routing_weights[indirect_path] = routing_weights_var[k + 1].x

		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					Zi = egress_bound[i]
					Zj = ingress_bound[j]
					Uij = max_tm[i][j]
					direct_utilization = routing_weights_var[0].x * Uij + routing_weights_var[i + 1].x * Zj + routing_weights_var[j + 1].x * Zi
					block_pair_utilization[i][j] = direct_utilization
		#print(block_pair_utilization)
		return routing_weights
	except GurobiError as e:
		print ("Bounded WCMP - Error code " + str(e. errno ) + ": " + str(e))
		return None
	except AttributeError :
		print ("Bounded WCMP - Encountered an attribute error ")
		return None	

## Bounded WCMP (simplified version)
def bounded_wcmp_path_weights_simplified(nblocks, link_capacity, logical_topology_adj_matrix, traffic_matrices):
	egress_bound = [0] * nblocks
	ingress_bound = [0] * nblocks
	## Step 1 : compute the pod egress and ingress bounds
	max_tm = np.zeros((nblocks, nblocks,))
	for tm in traffic_matrices:
		for pod in range(nblocks):
			pod_egress = sum(tm[pod])
			pod_ingress = 0
			for target_pod in range(nblocks):
				pod_ingress += tm[target_pod][pod]
				max_tm[pod][target_pod] = max(max_tm[pod][target_pod], tm[pod][target_pod])
			egress_bound[pod] = max(egress_bound[pod], pod_egress)
			ingress_bound[pod] = max(ingress_bound[pod], pod_ingress)


	# Step 2 : Initialize the optimization variables
	model = Model("Bounded WCMP")
	model.setParam( 'OutputFlag', False )
	mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=1, vtype=GRB.CONTINUOUS, name="mlu")
	w0 = model.addVar(lb=0., ub=1, obj=0, vtype=GRB.CONTINUOUS, name="w0")
	wi = model.addVar(lb=0., ub=1, obj=0, vtype=GRB.CONTINUOUS, name="wi")

	## Step 3 : Start programming the constraints
	## Constraint Type 1 : weights must sum to 1
	weight_constraint = w0 + (nblocks - 2) * wi
	model.addConstr(lhs=weight_constraint,sense=GRB.EQUAL,rhs=1)

	## Constraint Type 2 : mlu constraint
	for i in range(nblocks):
		for j in range(nblocks):
			if i != j:
				Zi = egress_bound[i]
				Zj = ingress_bound[j]
				Uij = max_tm[i][j]
				mlu_constraint = (Uij * w0) + ((Zi + Zj) * wi)
				model.addConstr(lhs=mlu_constraint, sense=GRB.LESS_EQUAL, rhs=mlu * link_capacity * logical_topology_adj_matrix[i][j])
	
	## Step 4 : insert the objective function
	model.setObjective(mlu, GRB.MINIMIZE)
	try:
		model.optimize()
		print("Bounded WCMP - MLU : {}".format(mlu.x))
		routing_weights = {}
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					direct_path = (i, j)
					routing_weights[direct_path] = w0.x
					for k in range(nblocks):
						if k != i and k != j:
							indirect_path = (i, k, j)
							routing_weights[indirect_path] = wi.x
		routing_path_sum = (w0.x + (nblocks - 2) * wi.x)
		print("Direct path weight : {}\nIndirect path weight : {}\nTotal weights : {}".format(w0.x, wi.x, routing_path_sum))
		return routing_weights
	except GurobiError as e:
		print ("Bounded WCMP - Error code " + str(e. errno ) + ": " + str(e))
		return None
	except AttributeError :
		print ("Bounded WCMP - Encountered an attribute error ")
		return None	


def dijkstra(graph_nodes):
	num_nodes = len(graph_nodes.keys())
	visited = {} 
	distance = {}
	for node in graph_nodes.keys():
		distance[node] = sys.maxint
		visited[node] = False
	curr_node = graph_nodes.keys()[0]
	distance[curr_node] = 0
	visited[curr_node] = True
	queue = []
	queue.append(curr_node)
	while len(queue) > 0:
		curr_node = queue.pop()
		visited[curr_node] = True
		for neighbor in graph_nodes[curr_node].keys():
			distance[neighbor] = min(distance[neighbor], distance[curr_node] + 1)
			if not visited[neighbor]:
				queue.append(neighbor)
	return visited, distance



## Bounded WCMP (enhanced version)
def bounded_wcmp_path_weights_enhanced(nblocks, link_capacity, logical_topology_adj_matrix, traffic_matrices):
	egress_bound = [0] * nblocks
	ingress_bound = [0] * nblocks
	## Step 1 : compute the pod egress and ingress bounds
	max_tm = np.zeros((nblocks, nblocks,))
	for tm in traffic_matrices:
		for pod in range(nblocks):
			pod_egress = sum(tm[pod])
			pod_ingress = 0
			for target_pod in range(nblocks):
				pod_ingress += tm[target_pod][pod]
				max_tm[pod][target_pod] = max(max_tm[pod][target_pod], tm[pod][target_pod])
			egress_bound[pod] = max(egress_bound[pod], pod_egress)
			ingress_bound[pod] = max(ingress_bound[pod], pod_ingress)


	## find out the maximum clique
	graph_nodes = {}
	for i in range(nblocks):
		for j in range(nblocks):
			if i != j:
				for k in range(nblocks):
					if k != i and k != j:
						graph_nodes[(i,k,j)] = {}

	## start inserting links
	for i in range(nblocks):
		for j in range(nblocks):
			if i != j:
				for k in range(nblocks):
					if k != i and k != j:
						graph_nodes[(k,i,j)]
						for kk in range(nblocks):
							if kk != i and kk != j and kk != k:
								graph_nodes[(kk,i,j)][(k,i,j)] = True
								graph_nodes[(k,i,j)][(kk,i,j)] = True
								graph_nodes[(i,j,kk)][(i,j,k)] = True
								graph_nodes[(i,j,k)][(i,j,kk)] = True
	index = 0
	for i in range(nblocks):
		for j in range(nblocks):
			if i != j:
				routing_weights_path_index[(i, j)] = index
				index += 1
				for k in range(nblocks):
					if k != i and k != j:
						found_index_ijk = None
						found_index_kij = None
						for kk in range(nblocks):
							if kk != j and kk != j and kk != k:
								if (i,j,kk) in routing_weights_path_index:
									found_index_ijk = 1
	visited, distance = dijkstra(graph_nodes)
	max_dist = 0
	for entry in distance:
		max_dist = max(distance[entry], max_dist)
	print("Max distance of graph is : {}".format(max_dist))

	# Step 2 : Initialize the optimization variables
	model = Model("Bounded WCMP")
	model.setParam( 'OutputFlag', False )
	mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=1, vtype=GRB.CONTINUOUS, name="mlu")

	routing_weights_var = {}
	for i in range(nblocks):
		for j in range(nblocks):
			if i != j:
				direct_path_weight = model.addVar(lb=0., ub=1, obj=0, vtype=GRB.CONTINUOUS, name="w_{}_{}_direct".format(i, j))
				routing_weights_var[(i, j)] = direct_path_weight
				wkij = model.addVar(lb=0., ub=1, obj=0, vtype=GRB.CONTINUOUS, name="w_k_{}_via{}_indirect".format(j, i))
				wijk = model.addVar(lb=0., ub=1, obj=0, vtype=GRB.CONTINUOUS, name="w_{}_k_via{}_indirect".format(i, j))
				for k in range(nblocks):
					if k != j and k != i:
						#assert((k,i,j) not in routing_weights_var)
						#assert((i,j,k) not in routing_weights_var)
						routing_weights_var[(k,i,j)] = wkij
						routing_weights_var[(i,j,k)] = wijk

	## Step 3 : Start programming the constraints
	## Constraint Type 1 : weights must sum to 1
	for i in range(nblocks):
		for j in range(nblocks):
			if i != j:
				weight_sum_constraint = LinExpr()
				weight_sum_constraint += routing_weights_var[(i, j)]
				for k in range(nblocks):
					if k != j and k != i:
						weight_sum_constraint += routing_weights_var[(i, k, j)]
				model.addConstr(lhs=weight_sum_constraint, sense=GRB.EQUAL, rhs=1)

	## Constraint Type 2 : mlu constraint
	for i in range(nblocks):
		for j in range(nblocks):
			if i != j:
				Zi = egress_bound[i]
				Zj = ingress_bound[j]
				Uij = max_tm[i][j]
				w0 = routing_weights_var[(i, j)]
				wkij = None
				wijk = None
				for k in range(nblocks):
					if k != i and k != j:
						wkij = routing_weights_var[(k, i, j)]
						wijk = routing_weights_var[(i, j, k)]
						break
				mlu_constraint = (Uij * w0) + (wkij * Zj) + (wijk * Zi)
				model.addConstr(lhs=mlu_constraint, sense=GRB.LESS_EQUAL, rhs=mlu * link_capacity * logical_topology_adj_matrix[i][j])
	
	## Step 4 : insert the objective function
	model.setObjective(mlu, GRB.MINIMIZE)
	try:
		model.optimize()
		print("Bounded WCMP - MLU : {}".format(mlu.x))
		routing_weights = {}
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					direct_path = (i, j)
					path_weight_sum = 0
					routing_weights[direct_path] = routing_weights_var[direct_path].x
					path_weight_sum += routing_weights_var[direct_path].x
					for k in range(nblocks):
						if k != i and k != j:
							indirect_path = (i, k, j)
							routing_weights[indirect_path] = routing_weights_var[indirect_path].x
							path_weight_sum += routing_weights_var[indirect_path].x
		#print("Direct path weight : {}\nIndirect path weight : {}\nTotal weights : {}".format(w0.x, wi.x, routing_path_sum))
		return routing_weights
	except GurobiError as e:
		print ("Bounded WCMP - Error code " + str(e. errno ) + ": " + str(e))
		return None
	except AttributeError :
		print ("Bounded WCMP - Encountered an attribute error ")
		return None	



